Baraj Sibiu, august 1996,  Ziua 1.
Problema 4 (Sume egale -Ion Maxim)

     Fie x1,x2,...,xn un sir de numere intregi, ordonat crescator.
     Sa se determine secventa din sirul dat, cu proprietatea ca numarul de
perechi de numere naturale, nenule (p,q) pentru care suma primelor p numere
din secventa este egala cu suma ultimelor q numere din secventa, este maxima.
     Datele de intrare se vor citi din fisierul text sir.txt, ce
contine elementele sirului, pe o linie, separate printr-un spatiu.
     Date de iesire vor fi afisate pe ecran sub forma :
Secventa : xu,xu+1,...,xv
(p1,q1) (p2,q2) ... (ps,qs)
Sunt s perechi in secventa [u,v]
unde u,v reprezinta indicii elementelor de inceput si sfarsit
ale secventei determinate.
Exemplu:
Pentru sirul : 2 2 2 3 3 4 6 22 23 iesirea va fi :
Secventa : 2 2 3 3 4
(2,1) (3,2) (4,3) (5,5)
Sunt 4 perechi in secventa [2,6]
=======================================
Solutia 1 (Mihai Stroe)
var tl1,max,lung,s1,s2,nr,ii,jj,i,j,k,l,m,n:longint;
    tl2:longint absolute $0:$46c;
    fi,fo:text;
    s:string;
    a,x,y,xx,yy:array[1..1000]of longint;

procedure readdata;
begin
  assign(fi,'sir.txt');
  reset(fi);
  while not eoln(fi)do
        begin
          inc(n);
          read(fi,a[n]);
        end;
end;

procedure solve;
begin
  max:=1;ii:=1;jj:=1;xx[1]:=1;yy[1]:=1;
  for lung:=n downto 1 do
      for i:=1 to n-lung+1 do
          begin
            j:=i+lung-1;
            if tl2-tl1>100 then exit;
            nr:=0;
            k:=i;
            l:=j;
            s1:=a[i];
            s2:=a[j];
            while(k<=j)and(l>=i)do
              begin
                if s1=s2 then
                   begin
                     inc(nr);
                     xx[nr]:=k-i+1;yy[nr]:=j-l+1;
                     inc(k);dec(l);
                     s1:=s1+a[k];
                     s2:=s2+a[l];
                   end
                   else
                if s1<s2 then
                   begin
                     inc(k);s1:=s1+a[k];
                   end
                   else
                   begin
                     dec(l);s2:=s2+a[l];
                   end;
              end;
            if max<nr then
               begin
                 max:=nr;
                 x:=xx;
                 y:=yy;
                 ii:=i;
                 jj:=j;
               end;
          end;
end;

begin
  readdata;
  tl1:=tl2;
  solve;
  write('Secventa: ');
  for i:=ii to jj do
      write(a[i],' ');
  writeln;
  for i:=1 to max-1 do
      write('(',x[i],',',y[i],') ');
  i:=max;
  writeln('(',x[i],',',y[i],')');
  writeln('Sunt ',max,' perechi in secventa [',ii,',',jj,']');
  readln;
end.
--------------------------
Solutia 2 (Ovidiu gheorghioiu)
const nmax=1000;

var s:array[0..nmax] of longint;
    x:array[1..nmax] of longint;
    i,j,k,n,p,q,max,mi,mj,nn:integer;
    nume:string;
    f:text;

procedure citeste;
begin
     write('Numele fis. de intrare: ');readln(nume);
     assign(f,nume);reset(f);
     n:=0;
     s[0]:=0;
     while not seekeof(f) do begin
           read(f,k);
           inc(n);
           x[n]:=k;
           s[n]:=s[n-1]+k
     end;
     close(f);
end;

procedure rezolva;
begin
     max:=-1;
     for i:=0 to n-2 do
         for j:=i+1 to n do begin
             nn:=0;
             for p:=i+1 to j do
                 for q:=j-1 downto i do
                     if s[p]-s[i]=s[j]-s[q] then inc(nn);
             if nn>max then begin
                max:=nn;
                mi:=i;
                mj:=j
             end;
         end;
end;

procedure scrie;
begin
     write('Secventa:');
     for i:=mi+1 to mj do write(' ',x[i]);
     writeln;
     for p:=mi+1 to mj do
         for q:=mj-1 downto mi do
             if s[p]-s[mi]=s[mj]-s[q] then write('(',p-mi,',',mj-q,')');
     writeln;
     writeln('Sunt ',max,' perechi in secventa [',mi+1,',',mj,']');
end;

begin
     citeste;
     rezolva;
     scrie;
end.
--------------------------
Solutia 3 (Sergiu Stefanov)
{$A+,B-,D+,E-,F-,G+,I+,L+,N+,O-,P-,Q-,R-,S+,T-,V+,X+,Y+}
{$M 16384,0,655360}
Program Problema4_Stefanov;

Uses
  Crt;

Const
  nmax=1000;

Var
  A:Array[1..nmax] of Integer;
  S:Array[0..nmax] of Integer;
  N,I,J,k,l,c:Integer;
  Max,Is,Js:Integer;
  Fi:Text;

Function Sum(n1,n2:Integer):Integer;

Begin
  Sum:=S[n2]-S[n1-1]
End;

Begin
  ClrScr;
  Assign(Fi,'sir.txt');
  ReSet(Fi);
  S[0]:=0;
  While not SeekEoF(Fi) do
    Begin
      N:=0;
      While not SeekEoLN(Fi) do
        Begin
          Inc(N);
          Read(Fi,A[N]);
          S[N]:=S[N-1]+A[N];
        End;
      ReadLn(Fi);
      Max:=0;
      For i:=1 to N do
        For j:=i to N do
          Begin
            c:=0;
            For k:=i to j do
              For l:=i to j do
                If Sum(i,k)=Sum(l,j) then
                  Inc(c);
            If C>max then
              Begin
                is:=i;
                js:=j;
                max:=c
              End;
          End;
      Write('Secventa:');
      For i:=is to js do
        Write(' ',A[i]);
      WriteLn;
      For k:=is to js do
        For l:=is to js do
          If Sum(is,k)=Sum(l,js) then
            Write('(',k-is+1,',',js-l+1,')');
      WriteLn;
      WriteLn('Sunt ',max,' perechi in secventa [',is,',',js,']');
    End;
  Close(Fi)
End.
-------------------------
Solutia 4 (Mihai Badoiu)
{$A+,B-,D-,E-,F-,G+,I-,L-,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y-}
{$M 16384,0,655360}
const
	max=2048;
type
	tv=array[1..max] of record
		x,y:integer;
		end;
var
	n:integer;
	v:array[1..max] of integer;
	virfo:integer;
	xo:tv;
	la,lb:integer;

function min(a,b:integer):integer;
begin
	if a<b then
		min:=a
	else
		min:=b;
end;

procedure load;
var
	f:text;
begin
	assign(f,'sir.txt');
	reset(f);
	n:=0;
	while not seekeof(f) do
	begin
		inc(n);
		read(f,v[n]);
		end;
	close(f);
end;

procedure calc_x(a,b:integer);
var
	s1,s2,s3,i,j:integer;
	virf:integer;
	x:tv;
begin
	s1:=0;
	s2:=0;
	j:=b;
	virf:=0;
	for i:=a to b do
	begin
		s1:=s1+v[i];
		while s1>s2 do
		begin
			s2:=s2+v[j];
			dec(j);
			end;
		if s1=s2 then
		begin
			inc(virf);
			x[virf].x:=i-a+1;
			x[virf].y:=b-j;
			end;
		s3:=min(s1,s2);
		s1:=s1-s3;
		s2:=s2-s3;
		end;
	if virfo<virf then
	begin
		virfo:=virf;
		xo:=x;
		la:=a;
		lb:=b;
		end;
end;

procedure calc_x2(a,b:integer);
var
	s1,s2:longint;
	i,j:integer;
	virf:integer;
	x:tv;
begin
	s1:=0;
	s2:=0;
	virf:=0;
	for i:=a to b do
	begin
		s1:=s1+v[i];
		s2:=0;
		for j:=b downto 1 do
		begin
			s2:=s2+v[j];
			if s1=s2 then
			begin
				inc(virf);
				x[virf].x:=i-a+1;
				x[virf].y:=b-j+1;
				break;
				end;
			end;
		end;
	if virfo<virf then
	begin
		virfo:=virf;
		xo:=x;
		la:=a;
		lb:=b;
		end;
end;

procedure calcul;
var
	i,j:integer;
begin
	for i:=1 to n do
		for j:=i to n do
		if v[i]>0 then
			calc_x(i,j)
		else
			calc_x2(i,j);
end;

procedure scrie;
var
	i:integer;
begin
	write('Secventa: ');
	for i:=la to lb do
		write(v[i],' ');
	writeln;
	for i:=1 to virfo do
	begin
		write('(',xo[i].x,',',xo[i].y,')');
		end;
	writeln;
	writeln('Sunt ',virfo,' perechi in secventa [',la,',',lb,']');
end;

begin
	load;
	calcul;
	scrie;
end.
----------------------------
Solutia 5 (Valentin gheorghita)
program problema4;
uses crt;
var a,b,c:array[0..5200] of longint;
    f:text;
    t,l,n,i,p,q,j,k,max:integer;

begin
 clrscr;
 assign(f,'sir.txt');
 reset(f);
 i:=0;
 while(not(seekeof(f))) do
   begin
    i:=i+1;
    read(f,a[i]);
   end;
 close(f);
 n:=i;
 if a[1]=a[n] then begin
                    write('Secventa : ');
                    for i:=1 to n do
                     write(a[i],' ');
                     writeln;
                    for i:=1 to n do
                     write('(',i,',',i,') ');
                    writeln;
                    writeln('Sunt ',n,' perechi in secventa [',1,',',n,']');
                    halt;
                   end;
 b[1]:=a[1];
 c[n]:=a[n];
 b[0]:=0;
 c[0]:=0;
 a[0]:=0;
 a[n+1]:=0;
 c[n+1]:=0;
 b[n+1]:=0;
 for i:=2 to n do
  begin
   b[i]:=b[i-1]+a[i];
   c[n-i+1]:=c[n-i+2]+a[n-i+1];
  end;
 max:=0;
 for i:=1 to n do
  for j:=i+1 to n do
   begin
    k:=0;
    t:=j;
    l:=i;
    while l<=j do
     begin
      while b[l]-b[i-1]>c[t]-c[j+1] do t:=t-1;
      if b[l]-b[i-1]=c[t]-c[j+1] then begin k:=k+1; t:=t-1; end;
      l:=l+1;
     end;
    if k>max then begin
                   max:=k;
                   p:=i;
                   q:=j;
                  end;
 end;
 write('Secventa : ');
  for i:=p to q do
   write(a[i],' ');
 writeln;
 i:=p;
 j:=q;
 t:=j;
 l:=i;
 while l<=j do
  begin
   while b[l]-b[i-1]>c[t]-c[j+1] do t:=t-1;
   if b[l]-b[i-1]=c[t]-c[j+1] then begin write('(',l-i+1,',',j-t+1,') '); t:=t-1; end;
      l:=l+1;
     end;
 writeln;
 writeln('Sunt ',max,' perechi in secventa [',p,',',q,']');
end.
------------------------------------
Solutia 6 (Mihai Stroe)
    Pentru fiecare secventa sir[i],sir[i+1],...,sir[j] se calculeaza numarul
  de perechi (p,q) astfel: se porneste cu doua sume,s1 si s2, si cu doi indici
  k si l. Initial k=i,l=j,s1=sir[i],s2=sir[j]. Daca s1=s2, se incrementeaza
  numarul perechilor. Daca s1<s2, k creste cu 1, iar s1:=s1+sir[k]; daca
  s1>s2, l scade cu 1, iar s2:=s2+sir[l]. In final se gaseste secventa optima.
    Metoda are complexitate j-i+1 pe o secventa, deci n^3 pe toata problema,
  dar are dezavantajul ca functioneaza numai in cazul in care toate numerele
  sunt mai mari decit 0 (toate testele de la Sibiu); in caz contrar, se
  foloseste o metoda de complexitate n^3*log(n),pe care o expun in continuare.
    Initial, se calculeaza toate sumele primelor i elemente (0<i<=n); se poate
  calcula suma elementelor dintre pozitiile i si j scazind suma[i-1] din
  suma[j].
    Pe o secventa, complexitatea este n*log(n).
    Consideram sumele ultimelor q elemente din secventa. Acestea cresc de la
  stinga la dreapta daca sir[j-q+1] e negativ, ramin constante daca sir[j-q+1]
  este 0 si scad pentru sir[j-q+1] negativ.

    j-q+1       [] 0     g g+1 h h+1      j
    ------------[]---------------------------
    sir[j-q+1]  [] -x   -y 0   0 z       t            (x,y,z,t>0)
    ------------[]---------------------------
    suma[q]     []  <  < < = = = > > > > >

    Se determina g si h, prin cautare binara.
    Pentru fiecare suma a primelor elemente ale secventei, este cautata,
  prin cautare binara, o suma egala cu ea, cu j-q+1 intre 0 si g. Daca nu
  este gasita, se cauta si intre h+1 si j. Se verifica apoi daca suma este
  egala cu suma realizata pentru j-q+1=h+1, caz in care se adauga nu o
  pereche, ci h-g+1 perechi.
}

var tl1,max,lung,nr,ii,jj,i,j,k,l,m,n:longint;
    tl2:longint absolute $0:$46c;
    s1,s2:real;
    fi,fo:text;
    s:string;
    a:array[1..15003]of longint;
    x,y,xx,yy:array[1..50]of longint;

procedure readdata;
begin
  assign(fi,'sir.txt');
  reset(fi);
  while not seekeoln(fi)do
        begin
          inc(n);
          if n mod 1000=1 then writeln(n);
          read(fi,a[n]);
        end;
end;

procedure solve;
begin
  max:=1;ii:=1;jj:=1;xx[1]:=1;yy[1]:=1;
  for lung:=n downto 1 do
      for i:=1 to n-lung+1 do
          begin
            j:=i+lung-1;
            if tl2-tl1>1000 then exit;
            writeln(tl2-tl1);
            nr:=0;
            k:=i;
            l:=j;
            s1:=a[i];
            s2:=a[j];
            while(k<=j)and(l>=i)do
              begin
                if s1=s2 then
                   begin
                     inc(nr);
                     xx[nr]:=k-i+1;yy[nr]:=j-l+1;
                     inc(k);dec(l);
                     s1:=s1+a[k];
                     s2:=s2+a[l];
                   end
                   else
                if s1<s2 then
                   begin
                     inc(k);s1:=s1+a[k];
                   end
                   else
                   begin
                     dec(l);s2:=s2+a[l];
                   end;
              end;
            if max<nr then
               begin
                 max:=nr;
                 x:=xx;
                 y:=yy;
                 ii:=i;
                 jj:=j;
               end;
          end;
end;

begin
  readdata;
  tl1:=tl2;
  solve;
  write('Secventa: ');
  for i:=ii to jj do
      write(a[i],' ');
  writeln;
  for i:=1 to max-1 do
      write('(',x[i],',',y[i],') ');
  i:=max;
  writeln('(',x[i],',',y[i],')');
  writeln('Sunt ',max,' perechi in secventa [',ii,',',jj,']');
  readln;
end.
======================================
test 1:
2147483645 2147483645
-----------------------------
Test 2:
2 2 7 13 13
-------------------------
Test 3 (foarte mare)
--------------------------------
test 4:
1073741820 1073741821 1073741822 1073741823 2147483642 2147483644
-------------------------------------
test 5:
1073741820 1073741821 1073741822 1073741823 2147483642 2147483644
---------------------------

